package com.kitty.record.kittyalgorithm.audition;

import java.util.Calendar;
import java.util.Stack;

/**
 * 栈排序。
 * 编写程序，对栈进行排序使最小元素位于栈顶。
 * 最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。
 * 该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
 *
 * 示例1:
 * 输入：
 * ["SortedStack", "push", "push", "peek", "pop", "peek"]
 * [[], [1], [2], [], [], []]
 * 输出：
 * [null,null,null,1,null,2]
 *
 * 示例2:
 * 输入：
 * ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
 * [[], [], [], [1], [], []]
 * 输出：
 * [null,null,null,null,null,true]
 *
 * 说明:
 * 栈中的元素数目在[0, 5000]范围内。
 * @Author SHEN
 * @Date 2020/12/18
 */
public class LeetCode0305 {

    public static void main(String[] args) {

        SortedStack sortedStack = new SortedStack();

        sortedStack.push(3);
        sortedStack.push(5);
        sortedStack.push(6);
        sortedStack.push(8);
        sortedStack.push(6);
        sortedStack.push(2);
        sortedStack.push(0);

        System.out.println(sortedStack.toString());
        System.out.println(sortedStack.peek());


    }

    protected static class SortedStack {

        private Stack<Integer> stack;

        private Stack<Integer> tmp;

        public SortedStack() {
            this.stack = new Stack<>();
            this.tmp = new Stack<>();
        }

        public void push(int val) {
            if(this.stack.isEmpty()){
                this.stack.push(val);
                while (!this.tmp.isEmpty()){
                    this.stack.push(this.tmp.pop());
                }
            }else {
                while(!this.stack.isEmpty() && val > this.stack.peek()){
                    this.tmp.push(this.stack.pop());
                }
                this.stack.push(val);
                while (!this.tmp.isEmpty()){
                    this.stack.push(this.tmp.pop());
                }
            }
        }

        public void pop() {
            if(!this.isEmpty()){
                this.stack.pop();
            }
        }

        public int peek() {
            if(this.isEmpty()){
                return -1;
            }
            return this.stack.peek();
        }

        public boolean isEmpty() {
            return this.stack.isEmpty();
        }

        @Override
        public String toString() {
            return "SortedStack{" +
                    "stack=" + stack +
                    '}';
        }
    }


}


